package com.kjc.demo.basic.algorithmtest;

public class Test0924 {
	/**
	 * 	冒泡排序
	 * */
	public static void bullSort(int[] arr) {
		for(int i=0 ;i < arr.length-1 ;i ++) {
			for(int j = 0; j < arr.length -i -1 ; j++) {
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
	
	/**
	 * 选择排序
	 * */
	public static void selectSort(int[] arr) {
		for(int i=0; i< arr.length-1 ;i++){
			int min = i;
			for(int j = i+1 ; j< arr.length;j++) {
				if(arr[i] > arr[j]) {
					min = j;
				}
			}
			if(min != i) {
				int temp = arr[min];
				arr[min] = arr[i];
				arr[i] = temp;
			}
		}
	}
	
	/**
	 * 	插入排序
	 * */
	public static void insertSort(int[] arr) {
		for(int i = 1; i < arr.length; i++) {
			if(arr[i] < arr[i-1]) {
				int j = i;
				while(j > 0 && arr[j] < arr[j-1]) {
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
					j --;
				}
			}
		}
	}
	
	/**
	 * 	快速排序
	 * */
	public static void quickSort(int[] arr, int start ,int end) {
		int pre = arr[start];//以首位元素为基准位
		int i = start;
		int j = end;
		while(i < j) {
			while(i < j && arr[j] > pre) {
				j--;
			}
			
			while(i < j && arr[i] < pre) {
				i++;
			}
			
			if(i <j && arr[i] == arr[j]) {
				i++ ; 
			}else {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		if(i-1 >start) {
			quickSort(arr,start,i-1);
		}
		if(i+1 < end) {
			quickSort(arr, i+1 , end);
		}
		
	}
	
	/**
	 * 	堆排序
	 * */
	public static void heapSort(int[] arr) {
		for(int i= arr.length/2 -1; i>= 0 ;i--) {
			adjustHeap(arr,i,arr.length);
		}
		
		for(int j = arr.length-1;j>0;j--) {
			swap(arr,0,j);
			adjustHeap(arr,0,j);
		}
		
	}
	
	public static void adjustHeap(int[] arr,int i,int length) {
		int temp = arr[i];//先取出当前元素i
		for(int k = i *2 + 1; k<length ; k = k *2+ 1) {
			if(k+1 < length && arr[k] < arr[k+1]) {
				k ++;
			}
			
			if(arr[k] > temp) {
				arr[k] = arr[i];
				i = k;
			}else {
				break;
			}
		}
		arr[i] = temp;
	}
	
	public static void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public static void main(String[] args) {
		int[] arr = {2,3,45,6,7,8,9,3};
		bullSort(arr);
		printArr(arr);
		int[] arr1 = {2,3,45,6,7,8,9,3};
		selectSort(arr1);
		System.out.println("选择排序-------");
		printArr(arr1);
		System.out.println("插入排序");
		int[] arr2 = {2,3,45,6,7,8,9,3};
		insertSort(arr2);
		printArr(arr2);
		System.out.println("快速排序");
		int[] arr3 = {2,3,45,6,7,8,9,3};
		quickSort(arr3,0,arr3.length-1);
		printArr(arr3);
		System.out.println("堆排序");
		int[] arr4 = {2,3,45,6,7,8,9,32};
		heapSort(arr4);
		printArr(arr4);
	}
	
	public static void printArr(int[] arr) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i] + ",");
		}
	}
}
